/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/trapping-rain-water-ii
   @Language: C++
   @Datetime: 19-03-28 10:41
   */

class Solution {
	struct Point{
		int x, y, h;
		Point (int x, int y, int h){
			this->x=x, this->y=y, this->h=h;
		}
		bool operator<(const Point &a)const{
			return this->h > a.h;   // min heap
		}
	};
public:
	/**
	 * @param heights: a matrix of integers
	 * @return: an integer
	 * Tip:
	 * BFS
	 */
	int trapRainWater(vector<vector<int> > &heights) {
		// write your code here
		if(heights.size()<3 || heights[0].size()<3) return 0;
		int n=heights.size(), m=heights[0].size();
		priority_queue<Point> points;
		vector<bool> visit(n*m,false);
		for(int i=0; i<m; ++i){
			points.push(Point(0,i,heights[0][i]));
			points.push(Point(n-1,i,heights[n-1][i]));
			visit[i]=true;
			visit[(n-1)*m+i]=true;
		}
		for(int i=1; i<n-1; ++i){
			points.push(Point(i,0,heights[i][0]));
			points.push(Point(i,m-1,heights[i][m-1]));
			visit[i*m]=true;
			visit[i*m+m-1]=true;
		}
		int trap=0;
		vector<pair<int,int> > direct={{0,1},{1,0},{-1,0},{0,-1}};
		for(; points.size(); ){
			Point p=points.top();
			points.pop();
			for(const auto &d:direct){
				int x=p.x+d.first, y=p.y+d.second;
				if (x>0 && x<n && y>0 && y<m){
					if (visit[x*m+y]) continue;
					visit[x*m+y] = true;
					points.push(Point(x,y,max(p.h,heights[x][y])));
					trap += p.h>heights[x][y]?p.h-heights[x][y]:0;
				}
			}
		}
		return trap;
	}
};
